In recent years, telecommunications providers have generally been migrating their networks away from use of circuit switches, which have been the mainstay telephone switching devices for decades. Circuit switches connect to one another with circuits called trunks; one call uses one trunk for its entire duration. The newer switching technology is called a softswitch. A softswitch sends a call as packets over a packet switched network, such as an Internet Protocol (IP) network, when communicating to another softswitch. A softswitch and a circuit switch communicate over a trunk group (a set of trunks).
Telecommunications providers are adopting IP network technologies primarily to lower costs. IP-based equipment itself is often cheaper than its circuit-switched counterpart. In addition, providers hope to gain economies of scale by carrying different traffic types (voice, data, video, etc.) on the same IP infrastructure instead of on separate networks. As part of the evolution from a circuit-switched backbone to a packet-switched backbone, providers generally use only softswitches as intermediate nodes between backbone switches. Circuit switches do not serve as intermediate transit points for other pairs of backbone switches.
Much of the migration from circuit switches to softswitches described above occurs as networks are expanded. As long distance and wireless traffic grow rapidly, so must the networks that carry this voice traffic. The problem of expanding telecommunications network facilities has received much attention over the last three decades. For example, work done in the 1970s generally addresses a dynamic, multiperiod, multifacility problem with discrete capacity addition sizes. This work is reflected in B. Yaged, “Minimum Cost Routing for Dynamic Network Models,” Networks 1, 193-224 (1973); N. Christofides, et al., “Optimal Expansion of an Existing Network,” Math. Prog. 6: 197-211 (1974); N. Zadeh, “On Building Minimum Cost Communication Networks over Time,” Networks 4: 19-34 (1974); P. J. Doulliez et al., “Optimal Network Capacity Planning: A Shortest Path Scheme,” Opns. Res. 23: 811-818 (1975), all of which are incorporated herein by reference in their entireties. Because of the complexity of the foregoing problem, as pointed out by M. Minoux, “Network Synthesis and Dynamic Network Optimization,” Anns. Discr. Math. 31: 283-324 (1987), incorporated by reference herein in its entirety, work starting in the late 1980s has focused on a variety of approaches to develop computationally efficient solution methods. These include A. Balakrishnan et al., “A Dual-Ascent Procedure for Large Scale Uncapacitated Network Design,” Opns. Res. 37: 716-740 (1989); A. Dutta et al., “A Multiperiod Capacity Planning Model for Backbone Computer Communications Networks,” Opns. Res. 40, 689-705 (1992); and S. G. Chang et al., “Telecommunications Network Topological Design and Capacity Expansion: Formulations and Algorithms,” Telecommun. Syst. 1, 99-131 (1993), all of which are incorporated herein by reference in their entireties.
H. Luss, “Operations Research and Capacity Expansion Problems: A Survey,” Opns. Res. 30, 907-947 (1982), incorporated herein by reference in its entirety, presented a survey of capacity expansion problems, including the early network expansion work. Luss identifies the three major decisions in capacity expansion problems as expansion sizes, expansion times, and expansion locations. In addition, for network capacity expansion problems, the flow routing must be determined.
Thus, typically, capacity expansion problems are multi-period, and capacity additions exhibit economies of scale, i.e., the average cost of a unit of capacity decreases with larger additions. Therefore, there is a trade-off between the lower unit cost of capacity and putting capacity in place before it is needed. A common approach ignores any constraints on capital availability in order to minimize the discounted cost of expansion. This is the right approach if one has access to, and can determine the cost of, capital, but for practical business planning models, capital costs are not always easy to determine. Moreover, in present times telecommunications providers generally do not enjoy unlimited access to capital for network expansion purposes.
Accordingly, business constraints make it desirable to reduce the expansion problem described above to a simpler special case. Specifically, it would be desirable to be able to minimize the capital outlay in the current period required to provide service for the next year, similar to solving a multi-period problem assuming a very high cost of capital. There are two other reasons why planning only one period ahead would be desirable. First, forecasts of demand patterns in a network are quite uncertain, especially several periods out. Second, the technologies for providing the capacity additions are evolving rapidly and their costs are dropping.
Further, it would be desirable to perform network planning that takes into account the features of a hybrid network, i.e., a network that combines at least one circuit-switched network with at least one packet-switched network. Such network planning would be particularly advantageous in facilitating the migration that is occurring from circuit-switched networks to packet-switched networks.